class Solution {
public:
    bool less(vector<vector<int>>& matrix,int target,int k){
        int l = 0;
        int n = matrix.size();
        int r = n - 1;
        
        int num = 0;
        while(l < n && r >= 0){
            if(matrix[l][r] > target){
                r--;
            }else{
                num += r+1;
                l++;
            }
        }
        return num >= k;
    }
                                        
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(less(matrix,mid,k)){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
};
